.-----------
| Pangki God
| Programmed By: Jason Allen Doucette
| URl: http://www.jasondoucette.com/ai.html#Pangki
| E-mail: jason@jasondoucette.com

Pangki God is a retrograde analysis endgame database solver created as a personal 
experiment to see if a simple perfect information two player game could be solved 
entirely.  It was chosen because it is know that the games entire game tree is composed 
of at most 3^16 (43,046,721) positions, which can easily fit into a standard desktop 
computers memory.  It is composed of two programs, each explained below:

SolvePangki.exe
---------------
This creates a perfect play database of the entire game tree of Pangki, and saves the 
results in a 41.05 MB file in the program's directory called PangkiEndGameDatabase.bin.

PLEASE NOTE: The creation of this database can take up to an entire day, depending on 
the speed of your computer (it takes 51 minutes on my Athlon XP 2500+), as the 
program is not optimized in any way.  In fact, it is a dumbed down version of the 
original program, which used some pre-calculated look up tables that requires over 370 
MB of RAM.  This was removed to allow people to run the solver on machines with only 
42 MB of RAM (and also on machines such as Windows 95 that cannot run programs 
that use more than 256 MB of code). This file is required for the PlayPangki.exe 
program.

PlayPangki.exe
--------------
This loads the pre-computed perfect play database (PangkiEndGameDatabase.bin) from 
the program's directory, and allows you to play Pangki with a display of the current 
positions score for each legal move.

The interface is a simple console interface.  At each prompt, you are given a board 
position that shows Xs and Os for the two players pieces.  THE SIDE TO MOVE IS 
ALWAYS X.  If this board position has legal moves for X, then the legal moves are 
listed below the position with the score of the side to move.  Moves denoted 'Optimal 
Play' are the best theoretically plays.  If any move results in a previously visited position, 
this will be stated.  To enter a command at the prompt, type in the command, and press 
ENTER.

The following commands are available: 

1.	A through x (x = letter distinguishing the last move in the move list): 
 
Makes the selected move, and inverses the board (i.e. all X's and O's are 
swapped after the move is made) so that the new side to move is X.  If you 
wish to use this program to play a game of Pangki, you will have to get used 
to the fact that the X's and O's swap after every move.  This is because the 
database is solved for side X to move, and this program was created only as an 
interface for the database.  A true Pangki playing program would not have 
much difficulty in hiding the technicalities of the database from the user. 

2.	R: 
 
Resets the board to the starting position. 

3.	Q: 
 
Quits the program. 

4.	P[x1][x2]..[x16] (where x1.. x16 = X, O, or a space  ): 
 
Creates a new position in which X is the side to move.  Type in the characters 
that represent the board position you wish to create, going from left to right, 
top to bottom - just as you read a page.  The program does not check for a 
legal number of pieces.  Every possible combination is accepted, because they 
all exist in the database. 

5.	K: 
 
Goes back one board position. 

6.	W: 
 
Goes forward one board position. 
 
Each board position that is created is stored in a list, starting with the original 
board position at index 0.  The next position is stored at index 1, then index 2, 
etc.  Every time a move is made (or a new position created), it is saved in the 
next higher board position.  If you play through a game as normal from the 
starting position, this creates a history of past positions in the game (indexed 
from 0..current position index  1).  In the move list for any board position, it 
will indicate if any of these moves returns to one of these prior positions.  This 
indicates a stalemated game if this move is made (even though there is no 
repetition of position in Pangki rules, if you repeat positions forever, the game 
will never end, and thus it is a drawn game as soon as both players get bored 
and agree to a draw).


